package dailyTopic;

import java.util.Arrays;

/**
 * @author zhangmin
 * @create 2021-07-14 11:00
 */
public class minAbsoluteSumDiff1818 {
    public int binary(int[] num,int target){
        int l=0,r=num.length-1;
        if (num[r]<target){
            return r+1;
        }
        while (l<r){
            int mid=(r-l)/2+l;
            if (num[mid]<target){
                l=mid+1;
            }else {
                r=mid;
            }
        }
        return l;
    }

    public int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        int mod=1000000007;
        int n=nums1.length;
        int[] num=new int[n];
        System.arraycopy(nums1,0,num,0,n);
        Arrays.sort(num);
        /*for (int nu:num) {
            System.out.println(nu);
        }*/
        int sum=0;
        int max=0;
        for (int i = 0; i <n; i++) {
            int d=Math.abs(nums1[i]-nums2[i]);
            //System.out.println("d="+d);
            sum=(sum+d)%mod;
            int j=binary(num,nums2[i]);
            //System.out.println("j="+j);
            if (j<n){
                max=Math.max(max,d-(num[j]-nums2[i]));
                //System.out.println("max="+max);
            }
            if (j>0){
                max=Math.max(max,d-(nums2[i]-num[j-1]));
                //System.out.println("max="+max);
            }
        }
        return (sum-max+mod)%mod;
    }

   /* public static void main(String[] args) {
        int[] nums1=new int[]{1,7,5};
        int[] nums2=new int[]{2,3,5};
        dailyTopic.minAbsoluteSumDiff1818 object=new dailyTopic.minAbsoluteSumDiff1818();
        System.out.println(object.minAbsoluteSumDiff(nums1,nums2));
    }*/
}
